package cn.edu.zzuli.hash;

public class HashTabTest {

    public static void main(String[] args) {
        Employee hash = new Employee(1, "halo");
        Employee hi = new Employee(2, "hi");
        Employee qi = new Employee(7, "qi");
        Employee hello = new Employee(1024, "hello");
        HashTab hashTab = new HashTab(6);
        hashTab.add(hash);
        hashTab.add(hi);
        hashTab.add(qi);
        hashTab.add(hello);
        hashTab.list();
        System.out.println(hashTab.find(13));
        hashTab.list();
    }

}

class HashTab {
    private EmployeeLinked[] linked;
    private Integer size;

    public HashTab(Integer size) {
        this.size = size;
        linked = new EmployeeLinked[size];
        //对数组中每个元素初始化
        for (int i = 0; i < size; i++) {
            linked[i] = new EmployeeLinked();
        }
    }

    public void add(Employee emp) {
        //首先使用散列函数根据传入的 emp.id ,计算存储在哪条链表
        int no = emp.id % size;
        linked[no].add(emp);
    }

    public void list() {
        //遍历的时候要遍历所有的数组链表
        for (int i = 0; i < size; i++) {
            linked[i].list(i);
        }
    }

    public Employee find(int id) {
        int no = id % size;
        return linked[no].findEmpById(id);
    }
}

//employee 链表
class EmployeeLinked {

    //头节点，指向第一个节点
    private Employee head;

    //向链表中添加新元素
    public void add(Employee node) {
        //如果头节点为null，那现在加入的元素就是头一个元素
        if (head == null) {
            head = node;
            return;
        }
        //不是第一个节点，那么我们就要定义一个辅助变量来找到最后一个节点
        Employee temp = head;

        //循环遍历到最后一个节点
        //如果temp.next == null,说明当前节点为最后一个节点
        while (temp.next != null) {
            // temp 指针后移，指向下一个节点
            temp = temp.next;

        }

        //将最后一个节点 next指向新的元素
        temp.next = node;
    }

    //遍历链表
    public void list(int i) {
        System.out.print("第"+ i +"条链表");
        if (head == null){
            System.out.println("->null");
            return;
        }

        Employee temp = head;

        while (temp != null) {
            System.out.print("->" + temp);
            temp = temp.next;
        }
        System.out.println();
    }

    public Employee findEmpById(int id) {
        if (head == null) {
            return null;
        }
        Employee temp = head;
        while (true) {

            if (temp.id == id) {
                return temp;
            }

            if (temp.next == null) {
                return null;
            }

            temp = temp.next;
        }

    }

}

class Employee {
    Integer id;
    String name;
    Employee next;

    public Employee(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
